/**
 * @program: leetcode096
 * @author: JCM
 * @create: 2023-02-20 11:04
 * @description:
 **/
public class Main {
    /**
     * 卡特兰数
     * 假设  n  个节点存在二叉排序树的个数是  G(n)，令  f(i)  为以 i 为根的二叉搜索树的个数
     * G(n) = f(1) + f(2) + f(3) + ... + f(n);
     * f(i) = G(i-1) * G(n-i)
     * 综合两个公式可以得到 卡特兰数 公式
     * G(n) = G(0)*G(n-1) + G(1) * G(n-2) + ... + G(n-1) * G(0)
     * @param n
     * @return
     */
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i < n+1; i++) {
            for(int j = 1; j < i+1; j++) {
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}
